package com.wc.alorithm.tree;

/**
 * @Author congege
 * @Description 树状数组
 * @Date Created in 2023/12/5-19:27
 */
public class TreeArray {
    static int maxN = (int) 1e5 + 10;
    static int a[] = new int[maxN];
    static int c[] = new int[maxN];
    static int n;


    // 更新点:在i位置上增加val
    private static void add(int i, int val) {
        for (; i <= n; i += lowBits(i)) {
            c[i] += val;
        }
    }

    // 计算最低的2^k
    private static int lowBits(int i) {
        return (-i) & i;
    }

    private static int preSum(int i) {
        int res = 0;
        for (; i >= 1; i -= lowBits(i)) {
            res += c[i];
        }
        return res;
    }

}
